home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power Programmierung
/
Power-Programmierung (Tewi)(1994).iso
/
magazine
/
drdobbs
/
ddjcompr
/
hstest
/
src
/
pq.c
< prev
next >
Wrap
C/C++ Source or Header
|
1991-04-18
|
4KB
|
211 lines
/**
*** PQ.C
*** fuer Beschreibung etc. siehe Dr. Dobb's 6'87
*** this has been modified slightly for huffman structures
**/
#include <STDIO.H>
#include "pq.h"
#include "huffman.h"
#define STATIC
#ifndef HUFFMANN
#define PQ_SWAP(p,ptr1,ptr2) (*p->swap)(ptr1,ptr2)
#define PQ_CMP(p,ptr1,ptr2) (*p->cmp)(ptr1,ptr2)
#else
/*
#define PQ_SWAP(p,ptr1,ptr2) huff_swap((void*)ptr1,(void*)ptr2)
STATIC void _fastcall huff_swap(struct huff_tab **c1,struct huff_tab **c2)
{
void *tmp;
tmp = *c1;
*c1 = *c2;
*c2 = tmp;
}
*/
#define PQ_SWAP(p,c1,c2) { \
void *tmp; \
tmp = *(struct hufftab **)c1; \
*(struct hufftab **)c1 = *(struct hufftab **)c2; \
*(struct hufftab **)c2 = tmp; }
#define PQ_CMP(p,ptr1,ptr2) ((int)(((*(struct huff_tab **)ptr2)->count - \
(*(struct huff_tab **)ptr1)->count ) ))
//#define PQ_CMP(p,ptr1,ptr2) huff_cmp((void*)ptr1,(void*)ptr2)
//
//STATIC int _fastcall huff_cmp(struct huff_tab **c1,struct huff_tab **c2);
//STATIC int _fastcall huff_cmp(struct huff_tab **c1,struct huff_tab **c2)
//{
// return (*c2)->count-(*c1)->count;
//}
#endif
/*****************************************************************/
STATIC void reheap_down(register PQ *p)
{
int parent;
int child;
char *pparent;
char *pchild;
char *psibling;
char *heap;
heap = p->heap;
for (parent = 0, child = 1; child < p->nitems; )
{
pparent = heap + (parent * p->itemsize);
pchild = heap + (child * p->itemsize);
if (child + 1 < p->nitems)
{
psibling = pchild + p->itemsize;
if (PQ_CMP(p,pchild, psibling) < 0)
{
pchild = psibling;
++child;
}
}
if (PQ_CMP(p,pparent, pchild) >= 0)
break;
PQ_SWAP(p,pparent, pchild);
parent = child;
child = (parent * 2) + 1;
}
}
/*****************************************************************/
STATIC void reheap_up(register PQ *p)
{
int parent;
int child;
char *pparent;
char *pchild;
char *heap;
child = p->nitems - 1;
heap = p->heap;
while (child > 0)
{
parent = (child - 1) / 2;
pchild = heap + (child * p->itemsize);
pparent = heap + (parent * p->itemsize);
if (PQ_CMP(p,pparent, pchild) >= 0)
break;
PQ_SWAP(p,pparent, pchild);
child = parent;
}
}
/*****************************************************************/
PQ *pq_create(numele, elesize, cmp, swap, initheap)
int numele;
int elesize;
int (*cmp)();
void (*swap)();
void *initheap;
{
register PQ *p;
void *malloc();
int heapsize;
heapsize = numele * elesize;
if (initheap)
{
if ((p = malloc(sizeof(PQ))) == NULL)
return NULL;
p->heap = initheap;
p->bottom = (char *)initheap + ((numele - 1) * elesize);
p->nitems = numele;
}
else
{
if ((p = malloc(sizeof(PQ) + heapsize)) == NULL)
return NULL;
p->heap = (char *) (p + 1);
p->nitems = 0;
p->bottom = p->heap - elesize;
}
p->cmp = cmp;
p->swap = swap;
p->itemsize = elesize;
p->maxitem = numele;
return p;
}
/*****************************************************************/
int pq_ins(register PQ *p,void *item)
{
int spaceavail = p->maxitem - p->nitems;
if (spaceavail > 0)
{
p->nitems++;
memcpy(p->bottom += p->itemsize, item, p->itemsize);
reheap_up(p);
}
return spaceavail;
}
/*****************************************************************/
int pq_del(register PQ *p,void *target)
{
int slots_in_use;
if (slots_in_use = p->nitems)
{
memcpy(target, p->heap, p->itemsize);
memcpy(p->heap, p->bottom, p->itemsize);
p->nitems--;
p->bottom -= p->itemsize;
reheap_down(p);
}
return slots_in_use;
}
/*****************************************************************/
char *pq_look(register PQ *p)
{
return p->heap;
}
/*****************************************************************/
int pq_numele(register PQ *p)
{
return p->nitems;
}